package 堆结构和堆排序;

import java.io.*;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/21
 */
public class Code01_HeapSort {

    public static int MAXN = 100001;
    public static int[] arr = new int[MAXN];
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br
                = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out
                = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int)in.nval;
        for(int i = 0; i < n; i++){
            in.nextToken();
            arr[i] = (int)in.nval;
        }
        heapSort1();
        for(int i = 0; i < n-1; i++){
            out.print(arr[i] + " ");
        }
        out.println(arr[n-1]);
        out.flush();
        out.close();
        br.close();
    }

    // 从顶到底建立大根堆，O(n * logn)
    // 依次弹出堆内最大值并排好序，O(n * logn)
    // 整体时间复杂度O(n * logn)
    public static void heapSort1(){
        for(int i = 0; i < n; i++){
            heapInsert(i);
        }
        int size = n;
        while(size > 1){
            swap(0, --size);
            heapIfy(0, size);
        }
    }

    // 从底到顶建立大根堆，O(n)
    // 依次弹出堆内最大值并排好序，O(n * logn)
    // 整体时间复杂度O(n * logn)
    public static void heapSort2(){
        for(int i = n-1; i >= 0; i--){
            heapInsert(i);
        }
        int size = n;
        while(size > 1){
            swap(0, --size);
            heapIfy(0, size);
        }
    }

    // i位置的数，向上调整大根堆
    //arr[i] = x, x是新来的, 往上看，直到不比父亲大，或者来到0位置（顶）
    public static void heapInsert(int i){
        //i -> 父：(i-1)/2
        while(arr[i] > arr[(i-1)/2]){
            swap(i, (i-1));
            i = (i-1)/2;
        }
    }

    // i位置的数: 变小了，又想维持大根堆结构
    // 向下调整大根堆
    // 当前堆的大小为size
    //   i    --->    右
    //左    右       左    i
    //                  左   右
    public static void heapIfy(int i, int size){
        //左孩子结点位置
        int l = 2*i+1;
        while(l < size){
            //有左孩子：l
            //右孩子：l+1
            //评选，最强的孩子，是哪个下标的孩子
            int best = arr[l] < arr[l+1] && (l+1) < size ? l+1 : l;
            //上面已经评选了最强的孩子，接下来看，当前的数和最强的孩子相比，最强下标是谁
            best = arr[best] > arr[i] ? best : i;
            if(best == i){
                break;
            }
            swap(i , best);
            i = best;
            l = 2*i+1;
        }
    }

    public static void swap(int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
